|
|
1.
求解0-1背包问题的混合贪婪遗传算法
陈桢, 钟一文, 林娟
计算机应用
2021, 41 (1):
87-94.
DOI: 10.11772/j.issn.1001-9081.2020060981
求解0-1背包问题（KP）的最优解的时候，传统遗传算法（GA）的局部求精能力不足而简单局部搜索算法的全局探索能力有限，针对上述问题，将这两个算法整合并提出了混合贪婪遗传算法（HGGA）。在GA全局搜索框架下增加局部搜索模块，并改进传统仅基于物品价值密度的修复算子，增加基于物品价值的贪婪混合选项，从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索，另一方面依靠GA的经典操作算子开拓全局搜索空间，从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试，结果表明在第一组15个测试用例中的12个上，HGGA能够百分百找到最优解，成功率达到80%；在第二组小规模数据集上，HGGA的性能明显好于其他同类GA和其他元启发算法；在第三组大规模数据集上，HGGA较其他元启发式算法具有更好的稳定性和高效性。
参考文献 |
相关文章 |
多维度评价
|
|
